1. Field of the Invention
The present invention relates generally to a method and apparatus for decreasing the speed of write operations in systems utilizing nonvolatile memory and particularly to decreasing the speed of write operations in such systems when performing random write operations.
2. Description of the Prior Art
With the advent of the digital information revolution, nonvolatile memory (or FLASH memory or EEPROM memory) has enjoyed considerable popularity within less than a decade. This is in large part due to the particular characteristics, known to those of ordinary skill in the art, attributed to nonvolatile memory, such as maintenance of information even when power is interrupted or disconnected.
Nonvolatile memory has a wide variety of utilization, some of which include digital cameras where they are used to store photographs, in digital format, for later editing or loading elsewhere and personal computers (PCs) where they are used to store various types of digital information.
One of the problems posing a constant challenge to those interested in using nonvolatile memory is known to be the speed of read and write operations. As after each write operation, which involves changing the state of only cells that are still at a logical one state, an erase operation is necessary prior to a subsequent write operation to the same location, it is clear that any improvements to the speed of a write operation proves to be an impressive improvement to the overall system performance.
By way of a brief background to the way in which information is organized within nonvolatile memory, the memory, which may be one or more integrated circuits, typically more than one, is prearranged into blocks with each block including a predetermined number of sectors and each sector including a predetermined number of bytes. A sector is identified by the system by a logical block address (LBA) but when it is to be written to or read from nonvolatile memory, it is identified by a physical block address (PBA). There is generally a known correspondence between LBAs and PBAs, which may be maintained in random access memory (RAM).
An individual block or an individual sector may be defined as an erasable unit depending on the user. For example, a sector might and typically does include 512 bytes of data and 16 bytes of overhead information and in a given application, during an erase operation, the entire sector may be erased, which include many cells. In fact, a number of sectors may be erased at a time, in which case, the user has probably designed the system so that one or more blocks are erased together.
In existing systems employing nonvolatile memory, two types of data are stored therein. One type is file system data, another type is user system data. File system data provides information to the operating system as to the location in which a file, which includes user data, is located. User system data is the contents of a file, each file is generally comprised of large blocks of data typically requiring sequential write operations. In sequential write operations, LBAs appear in sequential order, i.e. sequential sectors are being written thereto.
Write operations are generally initiated by a host that interacts with a controller to direct information in and out of the memory. Sectors, identified by the host, are written thereto in memory. In mass storage applications, the host may initiate two types of write operation, one is a sequential write operation, as discussed hereinabove, and the other is a random write operation. One method of random write operation is generally performed when updating file system data.
In the more recent Windows operating system, employed in most PCs and workstations, a new file system, referred to as “FAT32” (File Allocation Table 32) is utilized, which allows file systems of the size greater than 2 Gigabytes. Advantages allowed by using FAT32 include formatting cards used for various applications, such as digital cameras, that have much larger capacity than prior file systems would have allowed.
In FAT32 type file systems, a special sector, referred to as “FSInfo” (File System Information) is employed. The FSInfo sector is continuously updated with information regarding the location of the next free cluster. In effect, this saves the file system software (operating system) from having to search the FAT for the location of a free cluster, which can be a time-consuming task. Not only FSInfo sectors but certain types of sectors as well, are generally written or re-written thereto more often than types of sectors.
However, continuous writing or updating of these certain sectors that are written thereto more often than others has the side effect of slowing down the system performance, in general, as well as consuming much nonvolatile memory space thereby causing inefficiencies in the use of nonvolatile memory.
As stated above, nonvolatile memory is organized into sectors with a group of sectors comprising a block. A sector typically includes 512 bytes of user data and 16 bytes of overhead information and a block may include 256 sectors, although, a sector may have a different number of bytes and a block may have a different number of sectors.
In existing nonvolatile memory systems, when a sector is to be written thereto, a free block is first located. A logical block address (LBA) value is correlated with a new physical block address (PBA) addressing a free or available block in nonvolatile memory. At this point, the free found block is considered to be ‘open’ or ‘pending’, i.e. being written thereto with sector information. For the purposes of discussion, the free found block, having an ‘open’ or ‘pending’ status, will be referred to as block 0, identified by VLBA 0.
Next, a sector subsequent to that being written is examined and if it is found that the subsequent sector is sequential or belongs to the correlated VLBA block, i.e. block 0 (PBA 0), the sector information is written to the sector location within the same block. Succeeding sectors of information, which belong to the correlated VLBA block, i.e. block 0, continue to be written thereto until block 0 is no longer free and has no more free locations in which case a different free block, for example, block 10 identified by VLBA 10 (PBA 10), is designated to be written thereto. Now, if there are further writes or updates of an already written sector of block 0, they will be written or stored in block 10. In this case, all of the sector information that was not updated is moved from block 0 to block 10 and block 0 is ‘closed’ pending erasure thereof.
In the previous example, after block 0 is no longer free, and assuming the new write command has sector information, which belongs to the same VLBA block, i.e. block 0, and is now being updated, a different free block, for example, block 10, identified by VLBA 0 and VPBA 10, is designated to be written thereto and is thus used to store updated sector information. At this point, blocks 0 and 10 are ‘pending’ or ‘open’. If yet another write command is received commanding updating of sector information that does not belong to block 0 and thus corresponds to an LBA other than VLBA 0, yet another free block, i.e. block 20 identified by VLBA 1 and VPBA 20 is used to store such update. An example of sector information that does not belong to the same VLBA block would be non-sequential sectors relative to those sectors being stored in block 0 or block 10. In this example, if block 0 and therefore block 10 are each designated to store sectors 0-255 (LBA 0 . . . LBA 255), then a write to sector 614 (LBA 614) is considered a write to a sector that does not belong to the same VLBA block as that of block 0 or block 10. All of the sector information that was not updated however is moved from block 0 to block 10. Now, in this case, blocks 10 and 20 will be ‘open’ or ‘pending’ and block 0 will be ‘closed’. As explained in U.S. patent application Ser. No. 09/620,544, entitled “Moving Sectors Within A Block of Information In A Flash Memory Mass Storage Architecture” and filed on Jul. 21, 2000, and U.S. Pat. No. 5,845,313, entitled “Direct Logical Block Addressing Flash Memory Mass Storage Architecture,” and issued on Dec. 1, 1998.
Still using the same example as above, yet another scenario is the case where even prior to block 0 running out of free space, that is, while it remains free or has available sector locations, if the new write command is a write operation to one of the sectors that was already updated once, again, another block, such as block 10, is used to store the second update of the already once-updated sector information and subsequent sectors, to the extent they are in sequential order and/or belong to the same LBA group as that of block 0, are written to corresponding sector locations of block 10. Un-updated sectors of block 0 are eventually moved to block 10 and block 0 is ‘closed’, Block 10 remains ‘open’ or ‘pending’.
To this end, in the case where a block includes, for example, 256 sectors, a maximum of possible 255 move operations of sector information would have to be performed, which is quite time consuming and degrades system performance.
This is illustrated, in high-level block diagram form, in FIG. 1, where a nonvolatile memory system 10 is shown to include a block 12 for storing sector information. The block 12 is initially free and subsequently filled with sector information if and to the extent to which these sectors are sequential. Once a non-sequential sector is to be written, the sectors, with block 12, which include recent or ‘good’ information, are moved to the block 14, as shown by the arrow 16, which could be 255 move operations (read of 255 sectors from the old or previous block and write of the same to the new block). The move operation of the good or un-updated sectors of the previous block to the new block, are known to cause a 50% slower system performance in nonvolatile memory system.
Thus, the need arises for a system and method for minimizing the time required for performing writing operations of non-sequential sectors in the file system area of nonvolatile memory.